package me.seu.demo.algorithms;

/**
 * 求可变数组指定区间位置元素之和
 *
 *
 * @since 2021/2/22 下午5:05
 */
public class NumMutableArray {

    private int[] data;
    private int[] sum;

    /**
     * 即sum[i]存储nums[0...i-1]的和
     * sum(i, j) = sum[j + 1] - sum[i]
     */
    public NumMutableArray(int[] nums) {

        data = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            data[i] = nums[i];
        }

        sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
    }

    /**
     * 求数组区间元素和
     * sum(i, j) = sum[j + 1] - sum[i]
     *
     * @param i
     * @param j
     * @return
     */
    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }

    /**
     * 更新数组元素值
     *
     * @param index
     * @param val
     */
    public void update(int index, int val) {
        data[index] = val;
        for (int i = index + 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + data[i - 1];
        }
    }

}
